A number of technical challenges are encountered when transmitting data over communication channel(s). First, it is important that the bandwidth of the communication channel(s) is efficiently utilized. In addition, it is important that the data is protected against unintended or unauthorized access. Traditionally, these two challenges are addressed independently, using compression and encryption techniques, respectively. For example, when the data must be fully recovered by the intended recipient(s), it can be compressed using lossless compression algorithms, such as Huffman codes or Lempel-Ziv algorithms, and then encrypted using private key-based ciphers based on the DES (Data Encryption Standard) or AES (Advanced Encryption Standard) standards, or public key-based ciphers, such as those based on RSA encryption techniques.
If only one communication channel is used, a successful attack to obtain the encryption key will compromise the data completely. Thus, one would like to reduce the risk by using multiple communication channels to transmit the data. For example, if there are N communication channels available, the data can be broken into N parts, each of which is compressed and encrypted before transmission through one of the N channels. Thus, the attacker must break the encryption ciphers used in all N channels before compromising the data completely. However, with each cipher broken, the attacker learns at least part of the data. This partial security breach is still undesirable especially when the data is highly sensitive (for example, private information such as social security numbers).
When data security is of particular importance, the data should be compromised if and only if all N channels are compromised. In other words, partial security breaches are not allowed. Typically, this security constraint is satisfied using an (N, N) secret sharing scheme. See, for example, A. Shamir, “How to Share a Secret,” Communications of the ACM, Vol. 22, 612-13 (1979), incorporated by reference herein. Generally, (N, N) secret sharing schemes distribute the secret (i.e., the data) to N participants. However, a perfect secret sharing scheme requires that each share of the secret is as large as the secret itself. Thus, the total number bits to be transmitted using a perfect (N, N) secret sharing scheme is N times the length in bits of the compressed data. This increase in the number of bits to be transmitted may prove to be too costly from the point of view of bandwidth utilization.
To improve the protection of the data from a partial security breach, without achieving perfect secret sharing, one possible method is to (i) transform the data using an invertible transform, (ii) break the transformed data into N parts, and then (iii) compress and encrypt the N parts independently before transmission. The main drawback of this method is that the amount of information about the data obtained by the attacker as a result of breaking each cipher is still significant. For example, if the transform is an invertible Fourier transform, with each broken cipher, the attacker will acquire information about the data in the transform (frequency) domain.
A need therefore exists for improved methods and apparatus for distributing data over N communication channels (or storing data into N destinations).